# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from BuildTree import *


class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        self.ans = []
        self.cnt = []

        def dfs(node: TreeNode, level):
            if not node: return
            if level >= len(self.ans):
                self.ans.append(0)
                self.cnt.append(0)
            self.ans[level] += node.val
            self.cnt[level] += 1
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 0)
        return [self.ans[i] / self.cnt[i] for i in range(len(self.ans))]


if __name__ == '__main__':
    null = None
    root = build_tree_from_level_order([3, 9, 20, null, null, 15, 7])
    s = Solution()
    r = s.averageOfLevels(root)
    print(r)
